1. Field of the Invention
The present invention relates to techniques for encrypting and decrypting data. More specifically, the present invention relates to a scalable file system which is configured to efficiently maintain encrypted files.
2. Related Art
To ensure data is not lost prematurely, it is common to create multiple backup copies of the data. However, it is also desirable in some cases to ensure that a file, once deleted, is not recoverable. This can be a rather complicated task if backup copies of the data are created and stored at different locations.
This problem can be solved by only storing the data in encrypted form. In this way, destroying the data is a somewhat easier problem because only the key must be deleted. However, long-term user keys can, over time, be obtained by an adversary through compromise or coercion. To remedy this problem, it is possible for keys to be kept in tamper-resistant smart cards, in which case it is not feasible to covertly discover the keys. To delete the data, the user need only destroy the smart card. However, it is expensive to require every user to have a smart card and every computer to have a smart card reader.
A more-sophisticated technique for managing secret keys (developed by a company called “Disappearing Inc.”) uses a special server called an “ephemerizer” (also referred to as a “key manager”) whose job it is to create and destroy keys. A nice property of this technique is that the ephemerizer can be built so it does not see any data. However, the ephemerizer must create and store a key for every ephemerally-created message. This can involve storing a large amount of data if the system is used to encrypt many messages. (Also see a related system disclosed in U.S. Pat. No. 6,363,480, entitled “Ephemeral Decryptability,” by inventor Radia J. Perlman.)
This storage-space problem can be alleviated by modifying the ephemerizer so that it only maintains one key per expiration time, and having that key used across many users and many files. See U.S. patent application Ser. No. 10/959,928, filed on 5 Oct. 2004, entitled “Method and Apparatus for Using Secret Keys to Make Data Permanently Unreadable,” by inventor Radia J. Perlman. This application is hereby incorporated by reference to disclose how an ephemerizer operates.
A similar scheme, which uses public ephemerizer keys, is more secure, and more efficient because encryption does not require interaction with the ephemerizer. This scheme is described in pending U.S. patent application Ser. No. O′ 09/880,470, entitled, “Secure Ephemeral Decryptability,” by inventor Radia J. Perlman (filed 13 Jun. 2001), and in Sun Microsystems Laboratory Technical Report No. TR-2005-140, entitled, “The Ephemerizer: Making Data Disappear,” February 2005.
However, the above-described solutions do not solve a number of problems that arise while building a file system that stores data in encrypted form. The straightforward way to build such a file system is to have each file encrypted with a key K, chosen at random for that file. Then if that file is to expire, K is encrypted with an appropriate key eph of the ephemerizer (one that will expire at the appropriate time). For robustness, K could also be encrypted with another ephemerizer's key. So {K} eph1, and (K)eph2 would be stored, in addition to the encrypted file. A logical place to store these encrypted keys is in the metadata for the file. However, since public keys are typically at least a thousand bits long, storing the key K encrypted with two ephemerizer keys would require about 2000 additional bits of storage space in the metadata. This significantly increases the size of the metadata and thereby significantly increases storage overhead of the file system.
The above-described solution also requires the file system to interact with the ephemerizer each time any file is opened, which increases communication overhead and also increases time required to open a file.
Hence, what is needed is a file system that facilitates making data disappear without the above-described problems.